package com.hr.leetcode.分治和递归和回溯;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 周恒哲
 * @date 2020/05/18
 * 四种解法：1、暴力法，双重循环，第二层计数
 *          2、map
 *          3、sort排序
 *          4、分治
 **/
public class _169_多数元素 {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int n=nums.length/2;
        int res=0;
        if (nums.length==0){
            return 0;
        }
        for (int num :nums) {
            if (!map.containsKey(num)){
                map.put(num,1);
            }else {
                map.put(num, map.get(num) + 1);
            }
        }
        System.out.println(map);
        for (Integer key:map.keySet()){
            if (map.get(key)>n){
                res=key;
            }
        }

        return res;
    }
    public int majorityElement2(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            //[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }


    public static void main(String[] args) {
       int[] arr={3,3,4};
       _169_多数元素 a=new _169_多数元素();
        int i = a.majorityElement(arr);
        System.out.println(i);
    }
}
